A point cloud is a data structure made up of a typically large set of point data, each descriptive of a point in three-dimensional space. Typically, points in a point cloud are arbitrarily distributed or seemingly random, i.e., are not distributed in a regular pattern. Thus, while point clouds can be directly rendered as an image of a collection of dots, point clouds do not lend themselves to image processing and/or other data manipulation techniques without first being modeled as a three-dimensional surface. When so modeled, the resulting structure is no longer a point cloud, per se, and suffers non-trivial data loss.
Generally, lossless data compression exploits redundancies by identifying and removing redundant data. Lossy compression identifies and removes insignificant or unimportant data to decrease the amount of data. Data compression of point clouds presents many challenges to the signal processing community. Very few effective compression techniques have been developed for point cloud data that preserve both the numerical and geometrical aspects of arbitrarily distributed three-dimensional data.
One point cloud compression technique transforms the point cloud into a network of different levels of triangles, each level being created by dividing the triangles of a prior level into smaller triangles. A bit plane encoder is used to generate bit planes from the layers of triangles, the collection of which realizes the compressed point cloud. One drawback of such a technique is that point cloud must first be modeled as a surface; the original point cloud data is essentially lost. Once decompressed, the modeled surface data is prone to artifacts that can lead to misleading or false features, e.g., edge information.
Another technique attempts to leverage the sweeping nature of light detection and ranging (LIDAR) by forming tuples from several dimensions that characterize the point cloud. For example, such tuples may include an ordinal reference that is indicative of the order in which the data of the tuple were collected, locations detected (x, y, and z), time, intensity, the number of reflected signals that return, the numerical reference of a particular reflected signal that returns, and so on. A sequence of vectors composed of the dimensions contained in the tuples is formed and a time series is generated from the vectors from the measured time at successive periods and spaced at relatively uniform time intervals. Wavelet analysis and transformation is performed on the time sequence of vectors to produce the compressed point cloud. This technique relies heavily on the assumption that the data channels are interrelated or correlated, and that this relationship can be modeled by a mathematical equation. For the cases in which such relationship doesn't exist, only a marginal compression can be expected. Moreover, this technique relies on the manner in which the data were acquired, e.g., the scene scanning patterns utilized during collection, and is thus both platform and mission dependent, as opposed to being applicable to point clouds in general. Moreover, applying a fixed mathematical model or equation to define such an interrelationship introduces approximation errors, which are inherent to data fitting algorithms in general.
There is thus an apparent need for point cloud processing that provides reasonable compression rates while retaining the original point cloud structure.